Detecting certain bit patterns in a bit-string alone or as a result of an operation of two bit-strings is very important in applications such as computer arithmetic hardware design. For example, leading one detection circuits are widely used in computational hardware. In a floating point adder, the location of the first one is needed to properly normalize the result after the addition. In parallel computing systems such as content addressable memories, a task is presented to a large number of processors, each working on a different data set. For the purposes of this discussion, the term parallel processors denotes any hardware system in which a plurality of identical processors operates on a data set. The processors may be general purpose computers or relatively simple circuits. Some of the processors will have results to report back at the end of the computations. To avoid the problems of multiple processors reporting at the same time, each processor is connected to a bit in a register. Those processors wishing to report a result set the register bit to a one. The system then gives control to the processor having the first one in the register. When this processor is finished, it resets its bit. The system then searches for the next one in the register, and the process is repeated. In each of these applications, a register having G bits must be examined to determine the location of the first one relative to one end of the register.
Prior art attempts to solve this problem are computationally slow. In general, the prior art schemes require a time of order G gate delays to determine the location of the leading one in a register.
Another example of a bit pattern detection problem is that of finding the number of leading zeros when two bit-strings are added. This problem is encountered in floating point hardware.
Broadly, it is the object of the present invention to provide an improved circuit and method for detecting predetermined bit patterns.
It is another object of the present invention to identify the location of a bit pattern found within a bit string.
It is a further object of the present invention to provide a detector that can provide an answer in less than O(G) gate delays.
It is yet another object of the present invention to provide an improved circuit for determining the number of trailing zeros in a bit string.
These and other objects of the present invention will become apparent to those skilled in the art from the following detailed description of the invention and the accompanying drawings.